package graph

import "fmt"

// Matrix
// start到end的路径
// 0 0 0 0 0
// 0 1 0 0 0
// 0 1 1 1 0
// 1 0 1 0 1
//

type Point struct {
	I, J int
}

func Matrix(maze [][]int, start, end Point) *[]Point {
	//方向操作
	dirt := [][]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

	// 标记扫描过的节点
	row, col := len(maze), len(maze[0])
	visited := make([][]bool, row)
	for i := range visited {
		visited[i] = make([]bool, col)
	}
	visited[start.I][start.J] = true
	queue := []Point{start}

	cost := 1
ove:
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			pi, pj := queue[0].I, queue[0].J
			queue = queue[1:]
			for step := 0; step < 4; step++ {
				x, y := pi+dirt[step][0], pj+dirt[step][1]
				if x >= 0 && x < row && y >= 0 && y < col && !visited[x][y] {
					//碰壁
					if maze[x][y] == -1 {
						continue
					}

					n := Point{I: x, J: y}
					queue = append(queue, n)
					maze[x][y] = cost
					visited[x][y] = true
					if end.I == x && end.J == y {
						break ove
					}
				}
			}
		}
		cost++
	}

	res := []Point{end}

	cost--
	for i := cost; i >= 0; i-- {
		p := res[len(res)-1]
		for step := range dirt {
			x, y := p.I+dirt[step][0], p.J+dirt[step][1]
			if x >= 0 && x < row && y >= 0 && y < col && cost == maze[x][y] {
				res = append(res, Point{x, y})
				break
			}
		}
		cost--
	}
	return &res
}

func test() {

	maze := make([][]int, 4)
	for i := range maze {
		maze[i] = make([]int, 5)
	}
	maze[1][1] = -1
	maze[2][1] = -1
	maze[2][2] = -1
	maze[2][3] = -1
	maze[3][0] = -1
	maze[3][2] = -1
	maze[3][2] = -1
	start, end := Point{}, Point{I: 3, J: 4}

	fmt.Println(Matrix(maze, start, end))
}
